#include "binary_find.h"
// 返回target元素下标
int BinaryFindAny1(std::vector<int>& v, int target) {
  int len = v.size();
  int l = 0, r = len, mid;
  while (l < r) {  // 搜索区间[l,r)
    mid = l + (r - l) / 2;
    if (v[mid] == target)
      return mid;
    else if (v[mid] < target)
      l = mid + 1;
    else if (v[mid] > target)
      r = mid;
  }
  return -1;  // 表示没有找到target元素
}
int BinaryFindAny2(std::vector<int>& v, int target) {
  int len = v.size();
  int l = 0, r = len - 1, mid;
  while (l <= r) {  // 搜索区间[l,r]
    mid = l + (r - l) / 2;
    if (v[mid] == target)
      return mid;
    else if (v[mid] < target)
      l = mid + 1;
    else if (v[mid] > target)
      r = mid - 1;
  }
  return -1;  // 表示没有找到target元素
}

// 返回target元素下标。如果有多个元素值等于target，则返回最左的那个的下标。
int BinaryFindLeft1(std::vector<int>& v, int target) {
  int len = v.size();
  int l = 0, r = len, mid;
  while (l < r) {  // 搜索区间[l,r)
    mid = l + (r - l) / 2;
    if (v[mid] == target)
      r = mid;
    else if (v[mid] < target)
      l = mid + 1;
    else if (v[mid] > target)
      r = mid;
  }
  // 退出条件 l == r
  // 返回什么值，举一个只有一个元素等于target的特例来看看
  // return v[r - 1] == target ? r - 1 : -1;
  return v[r] == target ? r : -1;
}
int BinaryFindLeft2(std::vector<int>& v, int target) {
  int len = v.size();
  int l = 0, r = len - 1, mid;
  while (l <= r) {  // 搜索区间[l,r]
    mid = l + (r - l) / 2;
    if (v[mid] == target)
      r = mid - 1;
    else if (v[mid] < target)
      l = mid + 1;
    else if (v[mid] > target)
      r = mid - 1;
  }
  // 退出条件 l == r + 1
  // return v[r + 1] == target ? r+1 : -1;
  return v[l] == target ? l : -1;
}

// 返回target元素下标。如果有多个元素值等于target，则返回最右的那个的下标。
int BinaryFindRight1(std::vector<int>& v, int target) {
  int len = v.size();
  int l = 0, r = len, mid;
  while (l < r) {  // 搜索区间[l,r)
    mid = l + (r - l) / 2;
    if (v[mid] == target)
      l = mid + 1;
    else if (v[mid] < target)
      l = mid + 1;
    else if (v[mid] > target)
      r = mid;
  }
  // 退出条件 l == r
  return v[l - 1] == target ? l - 1 : -1;
  // return v[r - 1] == target ? r - 1 : -1;
}
int BinaryFindRight2(std::vector<int>& v, int target) {
  int len = v.size();
  int l = 0, r = len - 1, mid;
  while (l <= r) {  // 搜索区间[l,r]
    mid = l + (r - l) / 2;
    if (v[mid] == target)
      l = mid + 1;
    else if (v[mid] < target)
      l = mid + 1;
    else if (v[mid] > target)
      r = mid - 1;
  }
  // 退出条件 l == r + 1
  // return v[r] == target ? r : -1;
  return v[l - 1] == target ? l - 1 : -1;
}